/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"
#include <iostream>
using namespace std;

BTreeIndex::BTreeIndex()
{
    rootPid = -1;
	treeHeight = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
	openmode = mode;
	RC rc;
    if (rc = pf.open(indexname, mode) < 0) return rc;
	if(pf.endPid()!=0)
	{
	if (rc = pf.read(0, treeInfo_buffer) !=0) {cout<<"cannot read tree info\n"; return rc;}
	memcpy(&rootPid, treeInfo_buffer, sizeof(rootPid));
	memcpy(&treeHeight, treeInfo_buffer + sizeof(rootPid), sizeof(treeHeight));
	}

	if(rc = pf.write(0, treeInfo_buffer) !=0) return rc;
	rootPid = 1;
	PageId leafPid = 2;
	treeHeight = 1;
	BTNonLeafNode root;
	BTLeafNode	leaf;
	root.setLeftPtr(leafPid);
	root.write(rootPid, pf);
	leaf.write(leafPid, pf);

	return rc;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
	if(openmode == 'w')
	{
		char buffer[PageFile::PAGE_SIZE];
		*((int*)buffer) = rootPid;
		*((int*)(buffer+4)) = treeHeight;
		pf.write(0, buffer); 
	}
    return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    IndexCursor cursor;
	locate(key, cursor);
	BTLeafNode leaf;
	leaf.read(cursor.pid, pf);
	if(leaf.insert(key, rid) == 0){
	leaf.write(cursor.pid, pf);
	return 0;}
	BTLeafNode sibling;
	int siblingKey;
	leaf.insertAndSplit(key, rid, sibling, siblingKey);
	PageId siblingPid = pf.endPid();
	sibling.setNextNodePtr(leaf.getNextNodePtr());
	leaf.setNextNodePtr(siblingPid);
	leaf.write(cursor.pid, pf);
	sibling.write(siblingPid, pf);
	insertInParent(cursor.pid, siblingKey, siblingPid);
}

RC BTreeIndex::insertInParent(PageId leftPid, int midKey, PageId rightPid)
{
	if(leftPid == rootPid)
	{
		BTNonLeafNode root;
		root.setLeftPtr(leftPid);
		root.insert(midKey, rightPid);
		PageId newPid = pf.endPid();
		rootPid = newPid;
		root.write(newPid, pf);
		treeHeight++;
	}
	int height = treeHeight;
	int nodepid = rootPid;
	int parentPid = rootPid;
	BTNonLeafNode nonleaf;
	while(height > 0)
	{
		nonleaf.read(nodepid, pf);
		parentPid = nodepid;
		nonleaf.locateChildPtr(midKey, nodepid);
		if(nodepid == leftPid)
			break;
		height--;
	}
	nonleaf.read(parentPid, pf);
	if(nonleaf.insert(midKey, rightPid) == 0)
	{
		nonleaf.write(parentPid, pf);
		return 0;
	}
	BTNonLeafNode sibling;
	int siblingKey;
	nonleaf.insertAndSplit(midKey, rightPid, sibling, siblingKey);
	PageId siblingPid = pf.endPid();
	nonleaf.write(parentPid, pf);
	sibling.write(siblingPid, pf);
	insertInParent(parentPid, siblingKey, siblingPid);
	
}




/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{	
	cursor.pid = -1;
	cursor.eid = -1;																
	int height = treeHeight;
	int nodepid = rootPid;
	BTNonLeafNode nonleaf;
	while(height > 0)
	{
		nonleaf.read(nodepid, pf);
		nonleaf.locateChildPtr(searchKey, nodepid);
		height--;
	}
	BTLeafNode leaf;
	leaf.read(nodepid, pf);
	int eid;
	RC rc;
	rc = leaf.locate(searchKey, eid);
	cursor.pid = nodepid;
	cursor.eid = eid;
	return rc;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    if(cursor.pid >= pf.endPid() || cursor.pid < 0) return RC_INVALID_CURSOR;
	BTLeafNode leaf;
	leaf.read(cursor.pid, pf);
	RC rc;
	if(rc = leaf.readEntry(cursor.eid, key, rid) != 0) return rc;
	cursor.eid++;
	if(cursor.eid == leaf.getKeyCount())
	{
		cursor.eid = 0;
		cursor.pid = leaf.getNextNodePtr();
	}
	return 0;
}

/**
* Write rootPid & treeHeight to pagePid = 0
*/
RC BTreeIndex::updateTreeInfo() {
	// update rootPid and treeHeight
	memcpy(treeInfo_buffer, &rootPid, sizeof(rootPid));
	memcpy(treeInfo_buffer + sizeof(rootPid), &treeHeight, sizeof(treeHeight));
	return pf.write(0, treeInfo_buffer);
}

RC BTreeIndex::pointToSmallestKey(IndexCursor& cursor) {
	cursor.eid = 0; //no matter which node, the entry is always the first one, i.e. eid = 0
	if(treeHeight == 1) cursor.pid = rootPid; // treeHeight = 1 indicates that there is only 1 node in the tree, i.e. the root.
	else {
		int depth = 1;
		BTNonLeafNode Root;
		BTNonLeafNode * CurrentNode = &Root;
		PageId left_child = rootPid;
		while(depth < treeHeight-1)
		{
			CurrentNode->read(left_child, pf);
			CurrentNode->resetPtr();
			CurrentNode->buffer_ptr--;
			left_child = CurrentNode->buffer_ptr->pid;
			BTNonLeafNode LeftChild;
			CurrentNode = &LeftChild;
			depth++;
		}
		// after the while loop, the pointer CurrentNode is pointing at the last Non-leaf node.
		CurrentNode->read(left_child, pf);  // read the data in the last Non-leaf node
		CurrentNode->resetPtr(); 
		CurrentNode->buffer_ptr--;   // now buffer_ptr is pointing at the very beginning of the buffer (not the fist key entry)
		cursor.pid = CurrentNode->buffer_ptr->pid; // now cursor is pointing at the most left leaf node.
	}
		
	return 0;
}
